# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
head=ListNode(4)
head.next=ListNode(2)
head.next.next=ListNode(1)
head.next.next.next=ListNode(2)
# def sortList(head):
#     #哈希表用来存储key-value信息
#     dictionary=dict()
#     while head:
#         dictionary[head.val]=head
#         head=head.next
#     #获取keys
#     keys=list(dictionary.keys())
#     print(keys)
#     keys.sort()
#     print(keys)
#     #结果列表
#     head=ListNode()
#     headPro=head
#     for key in keys:
#         headPro.next=dictionary[key]
#         headPro=headPro.next
#     headPro.next=None
#     while head:
#         print(head.val)
#         head=head.next

#方法超时
def sortList(head):
    #直接手写排序算法来求解即可
    ans=[]
    while head:
        ans.append(head)
        head=head.next

    for i in range(len(ans)):
        min=i
        for j in range(i+1,len(ans)):
            if ans[j].val<ans[min].val:
                min=j
        temp=ans[min]
        ans[min]=ans[i]
        ans[i]=temp

    head=ListNode()
    headPro=head
    for i in ans:
        headPro.next=i
        headPro=headPro.next
    headPro.next=None
    while head:
        print(head)
        head=head.next
def sortList1(head):
    dictionary=dict()
    while head:
        nextPro=head.next
        #当前键值并不在字典中
        if head.val not in  dictionary.keys():
            #直接存储
            #存储的value形式是[头结点，尾节点]
            dictionary[head.val]=[head,head]
        else:
            #当前的键值存在于字典中
            dictionary[head.val][1].next=head
            dictionary[head.val][1]=head
            dictionary[head.val][1].next=None
        head=nextPro

    keys=list(dictionary.keys())
    keys.sort()
    print(keys)
    head=ListNode()
    headPro=head
    for key in keys:
        headPro.next=dictionary[key][0]
        headPro=dictionary[key][1]
    headPro.next=None
    while head:
        print(head)
        head=head.next
sortList1(head)